\subsection{Экспериментальные данные}

Эксперимент проводился на данных по бактерии \textit{E.coli} (Escherichia coli, кишечная палочка), полученных при её секвенировании на аппарате компании Illumina.

\textit{E.coli} давно уже является стандартной бактерией для тестирования ассемблеров. Не в последнюю очередь это обусловлено тем, что ее геном был большое количество раз собран по очень качественным и длинным ридам и известен целиком с высочайшей степенью точности. В дальнейшем будем называть этот геном эталонным.

Если и не самой показательной, то уж точно наиболее популярной из всех метрик качества сборки является так называемая N50. Применительно к нашей ситуации, ее можно определить так: это максимальное число $N$, такое что если рассматривать ребра графа, длина которых $\geq N$, то они покроют более $50$\%  эталонного генома. 

Входные данные представляют собой $14$ млн парных ридов длины $100$ с небольшим внутренним расстоянием $120$ нуклеотидов, обеспечивающих $600X$ кратное среднее покрытие генома.

Вначале, риды были пропущены через популярный инструмент для коррекции ошибок, Quake (\cite{KSS10, QURL}). Затем были изъяты из рассмотрения риды, содержавшие хотя бы один неизвестный нуклеотид, а также риды, парный к которым уже был отфильтрован. В результате, 30\% всех парных ридов было отброшено, но оставшиеся все еще составили $400X$ кратное покрытие.

Для эксперимента было выбрано значение $k=36$.

Результаты сравнивались с результатами запуска ассемблера Velvet с параметрами по-умолчанию на тех же данных. Velvet был выбран из-за того, что он также, как и наш ассемблер заботится о согласованности сопряженных элементов, а также реализует алгоритмы удаления тех же типов ошибочных участков графа. Причем алгоритмы, во многом более сложные чем наши.

Построение несжатого графа заняло 20 минут и потребовало всего 350Mb оперативной памяти. Приблизительно столько же заняли бы одни различные $k$-меры, встречающиеся в ридах. 

%сколько различных k-меров
После этого, сжатие графа заняло всего 140 секунд, а на хранение всей структуры сжатого графа потребовалось менее 10Mb.
Velvet построил граф приблизительно за то же время, при этом использовав $1.6$Gb оперативной памяти! 

Подсчет покрытия занял 10 минут.
И подсчет межреберных расстояний занял еще приблизительно 15 минут.

На хранение информации о межреберных расстояниях при отключенной кластеризации ушло 700Mb оперативной памяти.
При включенной кластеризации ``на лету'' с радиусом окрестности равным всего лишь 5, на хранение информации о межреберных расстояниях ушло менее 200Mb.

Построенный по ридам сжатый граф содержал 34641 ребер. ``Прикладыванием'' эталонного генома (и его комплементарного) к полученному графу было выяснено, что
\begin{itemize}
\item в графе содержится $99.98$\% $k$-меров, находящихся в эталонном геноме
%\item по тем ребрам, по которым проходит эталонный геном, он проходит всего лишь с 22 разрывами
\item 47\% ребер полученного графа (более 16 тыс.) не принадлежат к эталонному геному и являются ошибочными
\item N50 составляет всего лишь $1.6$kB
\end{itemize} 

Алгоритмы упрощения были запущены в режиме, не использующем последовательности на ребрах. Работа всех алгоритмов упрощения графа заняла менее 2 минут, что является более чем приемлемым результатом. В результате в графе осталось всего 3605 ребер (почти в 10 раз меньше изначального количества), при этом
\begin{itemize}
\item в графе все еще содержится $99.98$\% $k$-меров, находящихся в эталонном геноме 
\item только $1.9$\% всех ребер (68 штук) не принадлежит эталонному графу и являются ошибочными
\item N50 составляет $>24$kB
\end{itemize}

Процент $k$-меров эталонного генома, находящихся в графе изменился только лишь в 3-м знаке после запятой (было удалено только одно ребро, принадлежащее эталонному геному), что является показателем высокой точности работы наших алгоритмов, даже в режиме, предназначенном для бесконтекстного подхода и, не использующем последовательности нуклеотидов.
Из более чем 16 тыс. ошибочных ребер в графе осталось 68, то есть было удалено 99\% ошибочных ребер.
И наконец, полученное значение N50 полностью согласуется с тем, которое было получено Velvet.